package org.hhchat.leetcode.dp;

import java.util.Arrays;

/**
 * Created this one by HMH on 2017/6/12.
 * https://discuss.leetcode.com/topic/52302/1ms-java-dp-solution-with-detailed-explanation
 *
 * comb[target] = sum(comb[target-nums[i]]);
 */
public class code377 {
    public class Solution {
        private int[] dp;

        public int combinationSum4(int[] nums, int target) {
            dp = new int[target + 1];
            Arrays.fill(dp, -1);
            dp[0] = 1;
            return helper(nums, target);
        }

        private int helper(int[] nums, int target) {
            if (dp[target] != -1) {
                return dp[target];
            }
            int res = 0;
            for (int i = 0; i < nums.length; i++) {
                if (target >= nums[i]) {
                    res += helper(nums, target - nums[i]);
                }
            }
            dp[target] = res;
            return res;
        }
    }
}


// a faster one

//    public int combinationSum4(int[] nums, int target) {
//        int[] comb = new int[target + 1];
//        comb[0] = 1;
//        for (int i = 1; i < comb.length; i++) {
//            for (int j = 0; j < nums.length; j++) {
//                if (i - nums[j] >= 0) {
//                    comb[i] += comb[i - nums[j]];
//                }
//            }
//        }
//        return comb[target];
//    }